|
In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion〔.〕 is a characterization of planar graphs based on the properties of the depth-first search trees, published by 〔.〕〔.〕 and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm.〔.〕〔.〕 In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested.〔.〕 ==T-alike and T-opposite edges== For any depth-first search of a graph ''G'', the edges encountered when discovering a vertex for the first time define a depth-first search tree ''T'' of ''G''. This is a Trémaux tree, meaning that the remaining edges (the cotree) each connect a pair of vertices that are related to each other as an ancestor and descendant in ''T''. Three types of patterns can be used to define two relations between pairs of cotree edges, named the ''T''-alike and ''T''-opposite relations. In the following figures, simple circle nodes represent vertices, double circle nodes represent subtrees, twisted segments represent tree paths, and curved arcs represent cotree edges. The root of each tree is shown at the bottom of the figure. In the first figure, the edges labeled and are ''T''-alike, meaning that that, at the endpoints nearest the root of the tree, they will both be on the same side of the tree in every planar drawing. In the next two figures, the edges with the same labels are ''T''-opposite, meaning means that they will be on different sides of the tree in every planar drawing. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Left-right planarity test」の詳細全文を読む スポンサード リンク
|